package main

/*
堆排序法  主要解决优先队列的问题
时间复杂度：O(nlogn)
稳定性：不稳定
优点：
缺点：
出队入队时间：O(logn)

应用场景：操作系统动态选择优先级最高的任务执行。

堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：
即任何一非叶节点不大于或者不小于其左右孩子节点。
堆分为大顶堆和小顶堆

普通队列：先进先出，后进后出
优先队列：出队顺序和入队顺序无关，和优先级相关
*/

import "fmt"

type MaxHeap struct {
	data []int
	count int
}

func (m *MaxHeap) size() int {
	return m.count
}

func (m *MaxHeap) isEmpty() bool {
	return m.count == 0
}

func (m *MaxHeap) dd() {
	fmt.Println(m.data)
}

func (m *MaxHeap) insert(item int) {

	if m.data == nil {
		m.data = make([]int, 0)
		m.data = append(m.data, 0)
	}

	m.data = append(m.data, item)
	m.count++
	m.shiftUp(m.count)
}

func (m *MaxHeap) shiftUp(i int) {
	for i > 1 && m.data[i/2] < m.data[i] {
		swap(m.data, i, i/2)
		i = i/2
	}
}

func (m *MaxHeap) extractMax() int {

	max := m.data[1]
	swap(m.data, 1, m.count)
	m.data = m.data[:m.count]
	m.count--
	m.shiftDown(1)

	return max
}

func (m MaxHeap) shiftDown(i int) {

	for 2 * i < m.count {

		j := 2 * i

		if j + 1 <= m.count && m.data[j + 1] > m.data[j] {
			j += 1
		}

		if m.data[i] >= m.data[j] {
			break
		}

		swap(m.data, i, j)
		i = j

	}
}

// 数组建堆 时间复杂度O(n)
func (m *MaxHeap) heapify(arr []int) {

	m.data = make([]int, 0)
	m.data = append(m.data, 0)

	m.data = append(m.data, arr...)
	m.count = len(arr)

	for i := m.count / 2; i >= 1; i-- {
		m.shiftDown(i)
	}

}


func swap(slice []int, i int, j int) {
	if i == j {
		return
	}

	slice[i], slice[j] = slice[j], slice[i]
}

func main()  {

	max := MaxHeap{}

	array := []int{1, 3, 5, 7, 9, 11, 13}

	//for _, num := range array {
	//	max.insert(num)
	//}

	max.heapify(array)
	//max.dd()

	for !max.isEmpty() {
		fmt.Println(max.extractMax())
	}

}


